package Algorithm;

public class Work5 {
    /*动态规划*/

         /*大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项
         是1*/
        public int Fibonacci(int n) {
            if(n == 0){
                return 0;
            }
            int first = 1;
            int second = 1;
            int third = 1; //因为从0开始，third等于n就不用判定了
            while(n > 2){
                third = first + second;
                first = second;
                second = third;
                --n;
            }
            return third;
        }
        /*一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算
        不同的结果*/
        //方法一：简单动归方式-目前了解
        //状态定义：f(i): 跳到i台阶的总跳法
        //状态递推：f(i) = f(i-1)+f(i-2)
        //初始状态: f(0) = 1（0台阶，就是起点，到达0台阶的方法有一种，就是不跳[这里可能有点奇怪，但是想想，如果方法次数为0，就说明不可能开始...]）, f(1) = 1;

        public int JumpFloor1(int target) {
            int [] dp = new int[target+1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= target; i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[target];
        }

    //方法二：斐波那契数列

        public int JumpFloor2(int target) {
            int first = 1;
            int second = 2;
            int third = target;
            while(target > 2){
                third = first + second;
                first = second;
                second = third;
                --target;
            }
            return third;
        }
        /*我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩
         形，总共有多少种方法*/

        public int RectCover(int target) {
            if(target < 2){
                return target;
            }
            int [] dp = new int[target+1];
            dp[0] = 1;
            dp[1] = 1;
            dp[2] = 2;
            for(int i = 3; i <= target; i++){
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[target];
        }
        /*输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。*/
        public int NumberOf1(int n) {
            int count = 0;
            while(n != 0){
                n &= (n-1);
                count++;
            }
            return count;
        }

}
